In over-subscription planning, goals have utilities, actions have costs and the objective function is to find a plan satisfying a subset of goals that maximizes: (TotalGoalUtility−TotalActionCost). In many applications, goal utilities are not additive (i.e. not independent).
Classical planning aims at finding a plan that achieves a set of conjunctive goals. Partial satisfaction planning (PSP) relaxes this all-or-nothing constraint, focusing on finding a plan that achieves the “best” subset of goals (i.e. the plan that gives the maximum trade-off between total achieved goal utilities and total incurred action cost). The process of finding goals on which to focus is complicated by the fact that they interact with one another. For instance, actions may share in their achievement of goals (positive interaction) or conflict (negative interaction). These types of interactions introduce “cost dependencies” between goals because the total cost of achieving them separately may differ from the cost of achieving them together. In the existing frameworks, goals only interact through cost dependencies.
In reality, however, cost dependences are not the only types of dependencies that impact planning. Utility dependencies also impact planning. Two concrete examples of utility dependency are mutual dependency and conditional dependency. For mutual dependency, the utility of a set of goals is different from the sum of the utility of each individual goal. For example, (1) while the utility of having either a left or right shoe alone is zero, utility of having both of them is much higher (i.e. the goals “complement” each other); (2) utility of having two cars is smaller than the sum of the individual utilities of having each one of them (i.e. the goals “substitute” each other). Conditional dependency is where the utility of a goal or set of goals depend on whether or not another goal or set of goals is already achieved. For example, the utility of having a hotel reservation in Hawaii depends on whether or not we have already purchased a ticket to Hawaii.
The main technical challenges in handling utility dependencies are in finding (1) a model where different types of goal utility dependencies can be compactly expressed and (2) an approach that effectively combines utility interactions with cost interactions to find a high quality plan.
There has been work on PSP problems using orienteering to select goal subsets by David Smith. Also, van den Briel et al. introduced several planners such as AltAltPS, SapaPS, and Optiplan that tackle PSP by either greedily selecting goals up-front, heuristically searching for solutions, or compiling the problem into Integer Programming (IP). None of these planners deal with utility dependencies, however. The most recent International Planning Competition (Alfonso Gerevini, Blai Bonet and Bob Givan, Fifth international planning competition, IPC06 Booklet, 2006) included problems with preferences that involved indicating costs on plans that failed to meet preferred constraints. Also, PrefPlan (Ronen I. Brafman and Yuri Chernyavsky, Planning with goal preferences and constraints, Proceeding of ICAPS-05, 2005. can find optimal plans with preferences between goals.
There are several other known models such as UCP-Net (C. Boutilier, R. Brafman, H. Hoos and D. Poole, Reasoning with conditional ceteris paribus preference statements, Proc. Of UAI-2001, 2001.) and the graphical model. While both provide a graphical representation that can make it easier for users to understand dependencies, the GAI model is more general and these modeling methods can be compiled into GAI. We also note that PDDL3 (Alfonso Gerevini, Blai Bonet and Bob Givan, Fifth international planning competition, IPC06 Booklet, 2006) can represent GAI utility dependencies, albeit in an unnatural way.
It is possible to solve PSP problems by modeling them as MDPs and extracting a solution from an optimal policy. However, past experiments have shown this approach fails to scale well even when solving problems without utility dependencies on state-of-the-art MDP solvers.
The inventor is not aware of work using IP encoding in combination with greedy search for heuristic for planning. However, there has been work on using IP encoding to handle a subset of planning constraints involving continuous resource or temporal variables.
In combinatorial auctions, the utility for a set of items up for bid are normally non-additive and share many similarities with reasoning about sets of goals that are dependent in PSP. While a bidding process is different from planning, the bidding language can be used to represent utility dependencies in PSP_UD.
The presently described embodiments describe a method to solve the over-subscription planning problems where there are dependencies between goal utilities.